import sys
import math
from collections import Counter
from collections import defaultdict
def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()
def solve(arr):
pow = 1
ans = 0
temp = []
while 2 ** pow <= len(arr):
k = 2 ** pow
j = 0
cnt = 0
if temp:
arr = temp
temp = []
while j < len(arr):
t = []
cnt += 1
for i in range(k):
t.append(arr[j])
j += 1
if t != sorted(t):
ans += 1
t.sort()
for i in range(len(t) - 1):
if t[i+1] - t[i] != 1:
return -1
temp.extend(t)
pow += 1
return ans
t = int(input())
for _ in range(t):
n = get_ints()
arr = get_ints()
print(solve(arr))
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 300300;
int n, m;
int arr[MAXM];
int solve(int l, int r) {
if (r - l == 1) return 0;
int mid = (l + r) >> 1;
int mal = *max_element(arr + l, arr + mid);
int mar = *max_element(arr + mid, arr + r);
int ans = 0;
if (mal > mar) {
++ans;
for (int i = 0; i < (mid - l); ++i)
swap(arr[l + i], arr[mid + i]);
}
return solve(l, mid) + solve(mid, r) + ans;
}
int solve() {
int ans = solve(0, m);
if (is_sorted(arr, arr + m))
return ans;
return -1;
}
int main() {
int t; cin >> t;
while (t--) {
cin >> m;
for (int i = 0; i < m; ++i)
cin >> arr[i];
cout << solve() << endl;
}
}1698A - XOR Mixup | 1702E - Split Into Two Sets |
1703B - ICPC Balloons | 1702F - Equate Multisets |
1700A - Optimal Path | 665C - Simple Strings |
1708A - Difference Operations | 1703E - Mirror Grid |
1042A - Benches | 1676B - Equal Candies |
1705B - Mark the Dust Sweeper | 1711A - Perfect Permutation |
1701B - Permutation | 1692A - Marathon |
1066A - Vova and Train | 169B - Replacing Digits |
171D - Broken checker | 380C - Sereja and Brackets |
1281B - Azamon Web Services | 1702A - Round Down the Price |
1681C - Double Sort | 12A - Super Agent |
1709A - Three Doors | 1680C - Binary String |
1684B - Z mod X = C | 1003A - Polycarp's Pockets |
1691B - Shoe Shuffling | 1706A - Another String Minimization Problem |
1695B - Circle Game | 1702B - Polycarp Writes a String from Memory |